package com.yz.LinkList;

import java.util.Stack;

public class LinkListDemo {
    public static void main(String[] args) {
        HeroNode node1 = new HeroNode(1, "李白", "小李");
        HeroNode node2 = new HeroNode(2, "王伟", "小王");
        HeroNode node3 = new HeroNode(3, "白居易", "小白");
        LinkList linkList = new LinkList();
//        linkList.add(node1);
//        linkList.add(node2);
//        linkList.add(node3);
        linkList.addSort(node2);
        linkList.addSort(node1);
        linkList.addSort(node3);
        //没有反向打印之前的数据
        System.out.println("逆序之前的数据：");
        linkList.show();
        //逆序打印
        System.out.println("逆序之后的数据：");
        revserPrintf(linkList.getHead());

        //linkList.addSort(node2);
        System.out.println("反转之前");
        linkList.show();

        System.out.println("反转之后");
        reverList(linkList.getHead());
        linkList.show();
        HeroNode lastlist = Lastlist(linkList.getHead(), 1);
        System.out.println("返回的是倒数第一个的数据：" + lastlist);
        int count = count(linkList.getHead());
        System.out.println("单链表的节点个数为：" + count);
        System.out.println("修改节点之后的内容：");
        HeroNode heroNode = new HeroNode(2, "阿王", "王哥~");
        linkList.edit(heroNode);
        linkList.show();
        linkList.del(1);
        linkList.del(3);

        System.out.println("删除节点之后的内容：");
        linkList.show();
    }

    //获取单链表的节点个数,如果带头节点就返回null
    public static int count(HeroNode heroNode) {
        if (heroNode.next == null) {
            //这是一个空链表，直接返回
            return 0;
        }
        int length = 0;
        HeroNode temp = heroNode.next;
        while (temp != null) {
            length++;
            temp = temp.next;
        }
        return length;
    }

    //查找单链表的倒数第k个节点
    //思路
    //1。编写一个方法,接收head节点,同时接收一个index
    //2. index表示是倒数第index个节点
    //3。先把链表从头到尾遍历,得到链表的总的长度getLength
    //4。得到size后，我们从链表的第一个开始遍历(size-index)个,就可以得到
    public static HeroNode Lastlist(HeroNode heroNode, int index) {
        if (heroNode.next == null) {
            return null;
        }
        //第一次遍历得到链表的长度
        int size = count(heroNode);
        //第二次遍历得到倒数第几个节点
        //先做数据的校验
        if (index <= 0 || index > size) {
            //超过这个返回直接返回空
            return null;
        }
        //定义一个辅助变量来移动
        HeroNode temp = heroNode.next;

        for (int i = 0; i < size - index; i++) {
            temp = temp.next;
        }
        return temp;
    }

    //可以利用栈这个数据结构，将各个节点压入到栈中，
    //然后利用栈的先进后出的特点，就实现了逆序打印的效果
    public static void revserPrintf(HeroNode heroNode){
        //先创建一个栈
        Stack<HeroNode> stack = new Stack<>();
        //先判断链表是否为空
        if (heroNode.next == null){
            return;
            //System.out.println("该链表是空的！没有数据返回");
        }
        HeroNode temp = heroNode.next;
        while (temp != null){
            //将数据压入栈
            stack.push(temp);
            temp = temp.next;  //将节点后移动
        }
        //只要栈的长度大于0，就可以一直取出元素
        while (stack.size() > 0){
            //这样就可以取出元素
            System.out.println(stack.pop());

        }

    }





    //单链表的反转
    public static void reverList(HeroNode heroNode){
        //先判断链表是否为空，或者只有一个数据都返回自己
        if (heroNode.next == null || heroNode.next.next == null){
            return;
        }
        //先开始遍历老的链表
        //再将数据放入到新的链表中
        HeroNode newlist = new HeroNode(0,"","");
        //在定义一个临时变量
        HeroNode temp = heroNode.next;
        //指向当前节点的下一个节点
        HeroNode next = null;
        while (temp != null){
            next = temp.next;//先暂时保存当前节点的下一个节点，因为后面需要使用
            temp.next = newlist.next;//将temp的下一个节点指向新的链表的最前端
            newlist.next = temp; //新转过来的节点要连接新定义的链表
            temp = next;//让cur后移
        }
        //heroNode.next指向newlist.next ,实现单链表的反转
        heroNode.next=newlist.next;

    }



}


//创建一个单链表对象
class LinkList {
    //头结点不用动，初始化就可以了
    private HeroNode head = new HeroNode(0, "", "");

    //因为头结点是私有的，所以定义一个方法来返回
    public HeroNode getHead() {
        return head;
    }

    //添加节点到单向链表
    //思路,当不考虑编号顺序时
    public void add(HeroNode heroNode) {
        //1找到当前链表的最后节点
        //因为自己定义的head不能动。所以只能用一个辅助变量来操作
        HeroNode temp = head;
        while (true) {
            if (temp.next == null) {
                break;
            }
            //没有找到，就一直将temp后移
            temp = temp.next;
        }
        //2将最后这个节点的next指向新的节点
        //找到最后之后，就将元素添加进去
        temp.next = heroNode;
    }

    //删除链表的数据
    //传入的是该编号，然后通过编号来删除
    public void del(int no) {
        //由于head不能动，所以就定义一个临时变量
        HeroNode temp = head;
        Boolean flag = false;
        while (true) {
            if (temp.next == null) {
                //表示到达了链表的最后位置
                break;
            } else if (temp.next.no == no) {
                //表示找到了要删除的位置
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            //这是就表示找到了，并且要删除
            temp.next = temp.next.next;
        } else {
            System.out.printf("该链表中没有找到该编号为：%d的数据", no);
        }
    }

    //修改数据内容
    public void edit(HeroNode newHeronode) {
        //创建临时变量
        HeroNode temp = head;
        Boolean flag = false;
        while (true) {
            if (temp.next == null) {
                break; //到达了链表的最后位置了
            }
            if (temp.no == newHeronode.no) {
                //说明位置找到了，就是在这个位置进行插入
                flag = true;
                break;
            }
            //后移，遍历当前链表
            temp = temp.next;
        }
        if (flag) {
            //这是表示找到了
            //然后进行替换
            temp.name = newHeronode.name;
            temp.nickname = newHeronode.nickname;
        } else {
            //这表示没有找到
            System.out.printf("该链表中没有找到该编号为：%d的数据,不能进行修改！", temp.no);
        }

    }

    //使其排序有序
    public void addSort(HeroNode heroNode) {
        //由于头不能动，所以定义一个临时变量
        HeroNode temp = head;
        //来判断是否到达指定位置
        Boolean flag = false;
        while (true) {
            if (temp.next == null) {
                break; //到达了链表的最后位置了
            }
            if (temp.next.no > heroNode.no) {
                //说明位置找到了，就是在这个位置进行插入
                break;
            } else if (temp.next.no == heroNode.no) {
                //说明位置冲突，已经存在该编号
                flag = true;
                break;
            }
            //后移，遍历当前链表
            temp = temp.next;
        }
        //如果flag为真的话，那么就无法插入
        if (flag) {
            System.out.printf("该位置已经存在，%d位置无法插入\n", heroNode.no);
        } else {
            //插入到链表里
            heroNode.next = temp.next;
            temp.next = heroNode;
        }

    }

    //显示列表里面的数据
    public void show() {
        if (head.next == null) {
            //表示该链表是空的
            System.out.println("该链表是空的，无法展示");
            return;
        }
        HeroNode temp = head.next;
        while (true) {
            if (temp == null) {
                //说明已经遍历到最后一个
                break;
            } else {
                //接下来开始遍历
                //因为我们重写了toString方法，所以直接展示
                System.out.println(temp);
                //一定要将temp后移，要不然娶不到后面元素
                temp = temp.next;
            }
        }
    }
}

//这是创建一个英雄对象
class HeroNode {
    int no;
    String name;
    String nickname;
    HeroNode next;

    public HeroNode(int no, String name, String nickname) {
        this.no = no;
        this.name = name;
        this.nickname = nickname;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickname='" + nickname +
                '}';
    }
}
